/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\90.子集-ii.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-22 14:07:26
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-31 11:05:33
 */
/*
 * @lc app=leetcode.cn id=90 lang=cpp
 *
 * [90] 子集 II
 */

// @lc code=start
// class Solution {
// private:
//     vector<vector<int>> res;
// public:
//     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
//         vector<int> path;
//         sort(nums.begin(),nums.end());
//         backtrack(nums,path,0);
//         return res;
//     }

//     void backtrack(vector<int> &nums,vector<int> &path,int start)
//     {
//         res.push_back(path);
//         for(int i = start; i < nums.size() ; i++)
//         {
//             if(i > start && nums[i] == nums[i-1])
//             {
//                 continue;
//             }
//             path.push_back(nums[i]);
//             backtrack(nums,path,i+1);
//             path.pop_back();
//         }
//     }

// };

class Solution {
private:
    vector<vector<int>> res;
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> path;
        sort(nums.begin(),nums.end());
        backtrack(nums,path,0);
        return res;
    }
    void backtrack(vector<int> &nums,vector<int>& path,int start)
    {
        res.push_back(path);
        for(int i = start;i < nums.size();i++)
        {
            if(i > start  && nums[i] == nums[i - 1])
            {
                continue;
            }
            path.push_back(nums[i]);
            backtrack(nums,path,i+1);
            path.pop_back();
        }
    }



};
// @lc code=end

